package 图.最小生成树;

import 抽象数据类型.IndexMinPQ;
import 抽象数据类型.DirectedEdge;
import 抽象数据类型.EdgeWeightedGraph;

/**
 * @description:
 * @author: ywk
 * @date: 2021-08-11
 */
public class 最先生成树Prim算法的即时实现 {
    public class PrimMST {
        private DirectedEdge[] edgeTo; //距离树最近的边
        private double[] distTo;//distTo[w] = edgeTo[w].weight()
        private boolean[] marked;//
        private IndexMinPQ<Double> pq;//有效的横切边

        public PrimMST(EdgeWeightedGraph g) {
            edgeTo = new DirectedEdge[g.V()];
            distTo = new double[g.V()];
            marked = new boolean[g.V()];
            for (int v = 0; v < g.V(); v++) {
                distTo[v] = Double.POSITIVE_INFINITY;
            }
            pq = new IndexMinPQ<>(g.V());
            distTo[0] = 0.0;
            pq.insert(0, 0.0);
            while ((!pq.isEmpty())) {
                visit(g, pq.delMin());
            }
        }

        private void visit(EdgeWeightedGraph g, int v) {
            marked[v] = true;
            for (DirectedEdge e : g.adj(v)) {
                int w = e.other(v);
                if (marked[w]) {
                    continue;
                }
                if (e.weight() < distTo[w]) {
                    edgeTo[w] = e;
                    distTo[w] = e.weight();
                    if (pq.contains(w)) {
                        pq.changeKey(w, distTo[w]);
                    } else {
                        pq.insert(w, distTo[w]);
                    }
                }
            }
        }

    }
}
